#include <iostream>
#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/io.hpp>

int Fibonacci_n2(int n)
{
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return Fibonacci_n2(n - 1) + Fibonacci_n2(n - 2);
    }
}

int Fibonacci(int n)
{
    if (n <= 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    boost::numeric::ublas::matrix<int> m (2, 2);
    m(0, 0) = 1;
    m(0, 1) = 1;
    m(1, 0) = 1;
    m(1, 1) = 0;
    boost::numeric::ublas::matrix<int> res(2, 2);
    res(0, 0) = 1;
    res(0, 1) = 0;
    res(1, 0) = 0;
    res(1, 1) = 1;

    n = n - 1;

    while (n) {
        if (n & 1) {
            res = boost::numeric::ublas::prod(res, m);
        }

        m = boost::numeric::ublas::prod(m, m);
        n >>= 1;
    }

    return res(0, 0) * 1 + res(0, 1) * 0;
}

int main(int argc, const char *argv[])
{
    for (int i = 0; i <= 10; ++i) {
        std::cout << Fibonacci_n2(i) << " ";
    }

    std::cout << std::endl;

    for (int i = 0; i <= 10; ++i) {
        std::cout << Fibonacci(i) << " ";
    }

    std::cout << std::endl;

    unsigned int k = 1;
    unsigned int i = Fibonacci(++k);
    unsigned int j = Fibonacci(++k);

    while (j > i) {
        std::cout << k << "-" << j << std::endl;
        i = j;
        j = Fibonacci(++k);
    }

    return 0;
}
